package com.cjm.algorithm.leetcode.hash;

import java.util.HashMap;
import java.util.Map;

/**
 * 请你设计并实现一个满足LRU（最近最少使用）缓存， 约束的数据结构。
 * 实现LRUCache类：
 * LRUCache(int capacity)以正整数， 作为容量capacity初始化LRU缓存
 * int get(int key)如果关键字key存在于缓存中， 则返回关键字的值， 否则返回-1
 * void put(int key, int value)如果关键字key已经存在， 则变更其数据值value;如果不存在， 则向缓存中插入该组key-value。如果插入操作导致关键
 * 字数量超过capacity， 则应该逐出最久未使用的关键字。
 *
 * 函数get和put必须以o(1)的平均时间复杂度运行
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 *
 *
 * 具体的， 我们使用哈希表来存储【键值对】， 键值对的键作为哈希表的key， 而哈希表的value则使用我们自己封闭的Node类， Node同时作为双
 * 向链表的节点。
 *
 * 插入：
 * 检查当前键值对是否已经存在于哈希表
 * 如果存在， 则更新键值对， 并将当前键值对所对应的Node节点调整到链表头部（refresh操作）
 * 如果不存在， 则检查哈希表容量是否已经达到容量：
 *  没达到容量：插入哈希表， 并将当前键值对所对应的Node节点调整到链表头部（refresh操作）
 *  已达到容量：先从链表尾部找到待删除元素进行删除（delete）操作， 然后再插入哈希表， 并将当前键值对所对应的Node节点调整到链表
 *  头部（refresh）操作
 *
 * 查询：如果没有在哈希表中找到该key， 直接返回-1， 如果存在key， 则将对应的值返回， 并将当前键值对所对应的Node节点调整到链表
 * 头部（refresh操作）
 */
public class LRUCache {
    class Node {
        int k, v;
        Node l, r;

        Node(int _k, int _v) {
            k = _k;
            v = _v;
        }
    }
    int n;
    Node head, tail;
    Map<Integer, Node> map;

    public LRUCache(int capacity) {
        n = capacity;
        map = new HashMap<>();
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.r = tail;
        tail.l = head;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            refresh(node);
            return node.v;
        }
        return -1;
    }

    public void put(int key, int value) {
        Node node = null;
        if (map.containsKey(key)) {
            node = map.get(key);
            node.v = value;
        } else {
            if (map.size() == n) {
                Node l = tail.l;
                map.remove(l.k);
                delete(l);
            }
            node = new Node(key, value);
            map.put(key, node);
        }
        refresh(node);
    }

    private void delete(Node node) {
        if (node.l != null) {
            Node left = node.l;
            left.r = node.r;
            node.r.l = left;
        }
    }

    private void refresh(Node node) {
        delete(node);
        node.r = head.r;
        node.l = head;
        head.r.l = node;
        head.r = node;
    }
}
